//
//  Problem378.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/11.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 378. 有序矩阵中第 K 小的元素
 给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
 请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

 示例 1：
     输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
     输出：13
     解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
 示例 2：
     输入：matrix = [[-5]], k = 1
     输出：-5
 提示：
     n == matrix.length
     n == matrix[i].length
     1 <= n <= 300
     -109 <= matrix[i][j] <= 109
     题目数据 保证 matrix 中的所有行和列都按 非递减顺序 排列
     1 <= k <= n2
 */
@objcMembers class Problem378: NSObject {
    func solution() {
        print(kthSmallestEr([[1, 5, 9],
                           [10,11,13],
                           [12,13,15]], 8))
    }
    
    /*
     最小值数组：效率差
     1: 创建一个最小值数组 minList
     2: 每次取最小值，然后加入新的最小值
     */
    func kthSmallest(_ matrix: [[Int]], _ k: Int) -> Int {
        if matrix.count == 0 {
            return 0
        } else if matrix.count == 1, matrix[0].count == 0 {
            return 0
        }
        
        var sMatrix: [[Int]] = matrix
        var minList: [(Int, Int)] = [(0, 0)]
        
        var rowIndex: [Int] = Array(repeating: -1, count: matrix.count)
        rowIndex[0] = 0
        
        var n = 0
        var result = -1
        while n < k {
            result = popMinValue(&sMatrix, &minList, &rowIndex)
            n += 1
        }
        return result
    }
    
    // 抛出顶部，然后插入新的数据
    func popMinValue(_ matrix: inout [[Int]], _ minList: inout [(Int, Int)], _ rowIndex: inout [Int]) -> Int {
        // 删除顶部最小值
        let minValue = minList.removeFirst()
        let value = matrix[minValue.0][minValue.1]
        
        // 将最小值的右边数字插入到minList中
        if minValue.1 + 1 < matrix.count {
            let rightIndex = (minValue.0, minValue.1 + 1)
            let rightValue = matrix[minValue.0][minValue.1 + 1]
            var insertIndex = -1
            for (i, index) in minList.enumerated() {
                if matrix[index.0][index.1] >= rightValue {
                    insertIndex = i
                    break
                }
            }
            if insertIndex == -1 {
                minList.append(rightIndex)
            } else {
                minList.insert(rightIndex, at: insertIndex)
            }
        }
        rowIndex[minValue.0] += 1
        
        // 查看下一行是否在最小值数组中
        if minValue.0 < matrix.count-1, rowIndex[minValue.0+1] == -1  {
            
            let downIndex = (minValue.0+1, minValue.1)
            let downValue = matrix[downIndex.0][downIndex.1]
            var insertIndex = -1
            for (i, index) in minList.enumerated() {
                if matrix[index.0][index.1] >= downValue {
                    insertIndex = i
                    break
                }
            }
            if insertIndex == -1 {
                minList.append(downIndex)
            } else {
                minList.insert(downIndex, at: insertIndex)
            }
            
            rowIndex[downIndex.0] += 1
        }
        
        return value
    }
    
    /*
     二分法
     1：左上角是：最小值，右下角是：最大值，
     2: 那么计算这2个值的中间数mid，看看在数组中比中间数小的有几个 = count
     3: 加入count > k, 说明right = mid - 1, count < k => left = mid + 1
     4: count == k, 说明此时的mid满足条件，但是mid可能不在数组中，所以我们的还要继续计算，满足 == k的最小的那个就是我们要的值
     */
    func kthSmallestEr(_ matrix: [[Int]], _ k: Int) -> Int {
        var l = matrix.first!.first!
        var r = matrix.last!.last!
        var mid = 0
        var num = 0
        while l <= r {
            mid = l + (r - l) >> 1
            num = getNum(matrix, mid)
            print(l, r, mid, num, k)
            if num < k {
                l = mid + 1
            } else {
                r = mid - 1
            }
        }
        return l
    }
    
    // 获取数组中，小于等于value的个数
    func getNum(_ matrix: [[Int]], _ value: Int) -> Int {
        var i = matrix.count - 1
        var j = 0
        var result = 0
        while i >= 0, j < matrix.count {
            if matrix[i][j] <= value {
                j += 1
                result += i + 1
            } else {
                i -= 1
            }
        }
        return result
    }
}
